cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

, a distinguishing attack is any form of

cryptanalysis Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic sec ...

on data encrypted by a cipher that allows an attacker to distinguish the encrypted data from random data. Modern symmetric-key ciphers are specifically designed to be immune to such an attack. In other words, modern encryption schemes are pseudorandom permutations and are designed to have

ciphertext indistinguishability Ciphertext indistinguishability is a property of many encryption schemes. Intuitively, if a cryptosystem possesses the property of indistinguishability, then an adversary will be unable to distinguish pairs of ciphertexts based on the message th ...

. If an algorithm is found that can distinguish the output from random faster than a

brute force search In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the soluti ...

, then that is considered a break of the cipher. A similar concept is the

known-key distinguishing attack In cryptography, a known-key distinguishing attack is an attack model against symmetric ciphers, whereby an attacker who knows the key can find a structural property in cipher, where the transformation from plaintext to ciphertext is not random. ...

, whereby an attacker knows the key and can find a structural property in cipher, where the transformation from plaintext to ciphertext is not random.

Overview

To prove that a cryptographic function is safe, it is often compared to a random oracle. If a function would be a random oracle, then an attacker is not able to predict any of the output of the function. If a function is distinguishable from a random oracle, it has non-random properties. That is, there exists a relation between different outputs, or between input and output, which can be used by an attacker for example to find (a part of) the input. Example Let T be a sequence of random bits, generated by a random oracle and S be a sequence generated by a pseudo-random bit generator. Two parties use one encryption system to encrypt a message M of length n as the bitwise XOR of M and the next n bits of T or S respectively. The output of the encryption using T is truly random. Now if the sequence S cannot be distinguished from T, the output of the encryption with S will appear random as well. If the sequence S is distinguishable, then the encryption of M with S may reveal information of M. Two systems S and T are said to be indistinguishable if there exists no algorithm D, connected to either S or T, able to decide whether it is connected to S or T. A distinguishing attack is given by such an algorithm D. It is broadly an attack in which the attacker is given a black box containing either an instance of the system under attack with an unknown key, or a random object in the domain that the system aims to emulate, then if the algorithm is able to tell whether the system or the random object is in the black box, one has an attack. For example, a distinguishing attack on a

stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...

such as

RC4 In cryptography, RC4 (Rivest Cipher 4, also known as ARC4 or ARCFOUR, meaning Alleged RC4, see below) is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, ren ...

might be one that determines whether a given stream of bytes is random or generated by RC4 with an unknown key.

Examples

Classic examples of distinguishing attack on a popular stream cipher was by Itsik Mantin and

Adi Shamir Adi Shamir ( he, עדי שמיר; born July 6, 1952) is an Israeli cryptographer. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identifi ...

who showed that the 2nd output byte of RC4 was heavily biased toward zero. In another example,

Souradyuti Paul Souradyuti Paul (born 1976) is an Indian cryptologist. Formerly a member of COSIC, he is currently working as an associate professor at Indian Institute of Technology Bhilai and a Guest Researcher for the National Institute of Standards and Techno ...

and Bart Preneel of

COSIC The Computer Security and Industrial Cryptography research group, commonly called COSIC, is a research group at the Department of Electrical Engineering of KU Leuven, which is headed by Bart Preneel. Research Research and expertise in digital s ...

have shown that the XOR value of the 1st and 2nd outputs of

is also non-uniform. Significantly, both the above theoretical biases can be demonstrable through computer simulation.

and Bart Preneel, Analysis of Non-fortuitous Predictive States of the RC4 Keystream Generator. INDOCRYPT 2003, pp52 – 6
(PDF)

References

External links

Source

Indifferentiability
{{Cryptography navbox , block Cryptographic attacks

Overview

Examples

See also

References

External links